//////栈
typedef int TYPE;

typedef struct Stack {
        TYPE* array;
        int capacity;//容量
        int top;//栈顶（有效元素）
}Stack;

void StackInit(Stack* ps, int capacity);//初始化
void StackPush(Stack* ps, TYPE date);//入栈
void StackOut(Stack* ps);//出栈
void StackCheckCapacity(Stack* ps); // 扩容
TYPE StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取有效元素个数
int StackEmpty(Stack* ps);//检测是否为空
void StactDestory(Stack* ps);//销毁

//初始化
void StackInit(Stack* ps, int capacity){
        assert(ps);
        capacity = capacity < 0 ? 3 : capacity;
        ps->array = (TYPE*)malloc(sizeof(TYPE) * capacity);
        if (!ps->array)
               assert(0);
        ps->capacity = capacity;
        ps->top = 0;
        return;
}
//入栈(尾插)
void StackPush(Stack* ps, TYPE date) {
        //assert(ps);-扩容中已检查
        StackCheckCapacity(ps);//扩容检查
        ps->array[ps->top] = date;
        ps->top++;
        return;
}
//出栈（尾删）
void StackOut(Stack* ps)
{
        if (StackEmpty(ps))//检测是否为空
               return;
        (ps->top)--;
        return;
}
//扩容
void StackCheckCapacity(Stack* ps ) {
        assert(ps);
        if (ps->top == ps->capacity) {
               TYPE* tmp = (TYPE*)realloc(ps->array, sizeof(TYPE) * (ps->capacity) * 2);
               if (!tmp)
                       assert(0);
               ps->array = tmp;
               ps->capacity *= 2;
        }
        return;
}
//销毁
void StactDestory(Stack* ps) {
        assert(ps);
        if (ps->array) {
               free(ps->array);
               ps->array = NULL;
               ps->capacity = 0;
               ps->top = 0;
        }
        return;
}
//获取栈顶元素
TYPE StackTop(Stack* ps) {
        assert(ps);
        return ps->array[ps->top - 1];
}
//获取有效元素个数
int StackSize(Stack* ps) {
        assert(ps);
        return ps->top;
}
//检测是否为空
int StackEmpty(Stack* ps) {
        assert(ps);
        return ps->top == 0;
}
////////////////////////////////////////////////
typedef struct {
    Stack s1;//模拟入队列
    Stack s2;//模拟出队列
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue));
    if(!mq)
        assert(0);
    StackInit(&mq->s1, 3);
    StackInit(&mq->s2, 3);
    return mq;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj); 
    StackPush(&obj->s1, x);
    return;
}

int myQueuePop(MyQueue* obj) {
    assert(obj);
    int ret = 0;
    if(StackEmpty(&obj->s2)){
        while(StackSize(&obj->s1)){
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackOut(&obj->s1);//必须要删除s1的，否则s2为空时，将再次重复第一次的队头出队列
            }
    }
    ret = StackTop(&obj->s2);
    StackOut(&obj->s2); 
    return ret;
}

int myQueuePeek(MyQueue* obj) {
   assert(obj);
   if(StackEmpty(&obj->s2)){
        while(StackSize(&obj->s1)){
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackOut(&obj->s1);//必须要删除s1的，否则s2为空时，将再次重复第一次的队头出队列
        }
    }
   return StackTop(&obj->s2); 
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    // if(StackEmpty(&obj->s1)&&StackEmpty(&obj->s2))
    //     return true;
    // return false;
    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    assert(obj);
    StactDestory(&obj->s1);
    StactDestory(&obj->s2);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/